/*
 * @lc app=leetcode.cn id=576 lang=typescript
 *
 * [576] 出界的路径数
 */

// @lc code=start
function findPaths(
  m: number,
  n: number,
  maxMove: number,
  startRow: number,
  startColumn: number
): number {
  const dirs = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  let mod = 10 ** 9 + 7;
  let map: Map<string, number> = new Map();
  const dfs = (startRow: number, startColumn: number, maxMove: number) => {
    // 4个方向出界，找到1个结果
    if (startRow < 0 || startRow === m || startColumn < 0 || startColumn === n) {
      return 1;
    }
    // 最大移动次数为0，没有找到结果
    if (maxMove === 0) return 0;
    let ans = 0;
    // 记忆化存储的k，有3个变量
    let key = `${startRow}-${startColumn}-${maxMove}`;
    if (map.has(key)) return map.get(key);
    // 递归找其他4个方向
    for (let [x, y] of dirs) {
      let nx = startRow + x;
      let ny = startColumn + y;
      ans += dfs(nx, ny, maxMove - 1);
      ans %= mod;
    }
    map.set(key, ans);
    return ans;
  };

  return dfs(startRow, startColumn, maxMove);
}
// @lc code=end
